# -*- coding: utf-8 -*-
"""
优先队列
特点：
存入其中的每项数据，都另外附有一个数值，表示项的优先程度，称为优先级
任何时候访问或者弹出，总是当前结构中优先级最高的

"""
class ListPriorQueue:
    """基于顺序表的优先队列的实现
    顺序可用于表示优先级
    """
    
    def __init__(self):
        self.elements = []
        self.length = 0
        
    def is_empty(self):
        if self.length == 0:
            return True
        return False
    
    def enqueue(self, element):
        """入队
        特点：小元素在队列前，不考虑队满问题。在入队前就确定好入队位置
        """
        # 队空
        if self.is_empty():
            self.elements.append(element)
            self.length += 1
        # 有元素,且有序
        else:
            # 有元素时考虑临界状态：首元素、尾元素情况
            for i in range(len(self.elements)):
                # 中间元素情况
                if element <= self.elements[i]:
                    self.elements.insert(i, element)
                    self.length += 1
                    return
            # 尾元素情况
            self.elements.append(element)
            self.length += 1
        
    def dequeue(self):
        # 队空
        if self.is_empty():
            raise ValueError("queue is empty!")
        # 队不空
        element = self.elements.pop(0)
        self.length -= 1
        return element
    
    def print_all(self):
        """顺序显示队列
        """
        return self.elements
        

class HeapPriorQueue:
    """基于堆结构的优先队列
    实现基于小顶堆实现的优先队列
    """
    def __init__(self):
        self.elements = []
    
    def is_empty(self):
        if len(self.elements) == 0:
            return True
        return False
    
    def enqueue(self, element):
        # 队空
        if self.is_empty():
            self.elements.append(element)
        else: # 队有元素
            # 先插入元素，再作向上筛选，保证为堆
            self.elements.append(element)
            self.sift_up()
            
    def sift_up(self):
        """向上筛选
        """
        # 如果空树 或 只有一个节点
        if self.is_empty() or len(self.elements) == 1:
            return
        # 多节点树
        last = neighbor = 0              # 初始化last、以及last的neighbor的位置
        last = len(self.elements) - 1    # 确定last
        if last % 2 == 0:                # 确定neighbor
            neighbor = last - 1
        else:
            neighbor = None
        parent = (last - 1) // 2         # 确定parent
        # 确定交换的位置
        # 有兄弟节点
        while last != 0:
            if neighbor is not None:
                # 兄弟节点 < 尾节点
                if self.elements[neighbor] < self.elements[last]:
                    
                    if self.elements[neighbor] < self.elements[parent]:
                        # 交换元素
                        self.__swap(neighbor, parent)
                else: # 兄弟节点 > 尾节点
                    
                    if self.elements[last] < self.elements[parent]:
                        self.__swap(last, parent)
                    
            else:# 没有兄弟节点
                if self.elements[last] < self.elements[parent]:
                    self.__swap(last, parent)
            
            # 更新位置
            last = parent
            if last % 2 == 0:
                neighbor = last - 1
            else:
                neighbor = last + 1
            parent = (last - 1) // 2
    
    def dequeue(self):
        if self.is_empty():
            raise ValueError("queue is empty!")
        if len(self.elements) == 1:
            return self.elements[0]
        else: # 如果有多个元素
            # 弹出堆顶
            result = self.elements.pop(0)
            # 取堆尾元素作为新根元素
            self.elements.insert(0, self.elements[-1])
            # 向下筛选
            self.sift_down()
            return result
        
    def sift_down(self):
        """向下筛选
        """
    
    def __swap(self, index_a, index_b):
        temp = self.elements[index_a]
        self.elements[index_a] = self.elements[index_b]
        self.elements[index_b] = temp
